class Solution:
    def lastRemaining(self, n: int) -> int:
        if n == 1:
            return 1
        re = []
        while n!=1:
            re.append(n%2)
            n=n//2
        r = 1
        for i in range(len(re)-1, -1, -1):
            r = r *2
            if i%2 != 0 and re[i]!=1:
                r = r-1
        return r


if __name__ == '__main__':
    so = Solution()
    n = 9
    r = so.lastRemaining(n)
    print(r)
